#include <iostream>
#include <limits>
#include <memory>
#include <map>
#include <iterator>
#include <exception>

enum TErrorType {
	ET_NoError,
	ET_TooBigPriority,
	ET_RottenHandle
};

template<typename PriorityType, typename VertexData>
class BinomialHeap {

private:
	struct Node;
	struct NodeX;

public:

	class Handle {

		friend class BinomialHeap;

	public:
		Handle(const Handle& other) :
			ptr(other.ptr) {}

		Handle(std::weak_ptr<Node> otherPtr) :
			ptr(otherPtr) {}

	private:
		std::weak_ptr<Node> ptr;
		Handle();
	};

	BinomialHeap()
		: head(nullptr)
	{}

	BinomialHeap(std::shared_ptr<Node> h)
		: head(h)
	{}

	Handle BinomialHeap_Insert(PriorityType priority, VertexData data);

	void Binomial_Link(std::shared_ptr<Node> y, std::shared_ptr<Node> z);
	void BinomialHeap_Union(BinomialHeap<typename PriorityType, typename VertexData>& other);
	void BinomialHeap_Merge(BinomialHeap<typename PriorityType, typename VertexData>& other);

	VertexData BinomialHeap_ExtractMin();

	TErrorType BinomialHeap_DecreasePriority(Handle& handle, PriorityType newPriority);

private:

	struct Node {

		VertexData Data;
		PriorityType Priority;
		std::weak_ptr<Node> Parent;
		std::shared_ptr<Node> Sibling;
		std::shared_ptr<Node> Child;
		int Degree;

		Node(PriorityType priority, VertexData data)
			: Data(data), Priority(priority), Sibling(nullptr), Child(nullptr), Degree(0) {}
	};

	struct NodeX {

		std::shared_ptr<Node> Current;
		std::shared_ptr<Node> Previous;
		std::shared_ptr<Node> Next;

		NodeX(std::shared_ptr<Node> current)
			: Current(current), Previous(nullptr), Next(current->Sibling) {}
	};

	std::shared_ptr<Node> head;

};

template<typename PriorityType, typename VertexData>
typename BinomialHeap<PriorityType, VertexData>::Handle BinomialHeap<PriorityType, VertexData>::BinomialHeap_Insert(PriorityType priority, VertexData data)
{
	std::shared_ptr<Node> node(new Node(priority, data));
	BinomialHeap H(node);
	BinomialHeap_Union(H);
	Handle h(node);
	return h;
}

template<typename PriorityType, typename VertexData>
VertexData BinomialHeap<PriorityType, VertexData>::BinomialHeap_ExtractMin()
{
	if (head == nullptr)
	{
		throw std::logic_error("Heap is empty!\n");
	}

	std::shared_ptr<Node> z = head;
	PriorityType min = std::numeric_limits<PriorityType>::max();
	std::shared_ptr<Node> x;
	while (z != nullptr)
	{
		if (z->Priority < min)
		{
			min = z->Priority;
			x = z;
		}
		z = z->Sibling;
	}


	std::shared_ptr<Node> temp = head;

	if (x == head)
	{
		head = x->Sibling;
	}
	else
	{
		while (temp->Sibling != x)
		{
			temp = temp->Sibling;
		}
		temp->Sibling = x->Sibling;
	}

	temp = x->Child;
	std::shared_ptr<Node> prev = nullptr;
	while (temp != nullptr)
	{
		std::shared_ptr<Node> next = temp->Sibling;
		if (temp == x->Child)
			temp->Sibling = nullptr;
		else
			temp->Sibling = prev;
		if (next == nullptr)
			break;
		else
		{
			prev = temp;
			temp = next;
		}
	}
	BinomialHeap H(temp);
	BinomialHeap_Union(H);
	return x->Data;
}

template<typename PriorityType, typename VertexData>
void BinomialHeap<PriorityType, VertexData>::Binomial_Link(std::shared_ptr<Node> y, std::shared_ptr<Node> z)
{
	y->Parent = z;
	y->Sibling = z->Child;
	z->Child = y;
	++z->Degree;
}

template<typename PriorityType, typename VertexData>
void BinomialHeap<PriorityType, VertexData>::BinomialHeap_Merge(BinomialHeap<typename PriorityType, typename VertexData>& other)
{
	std::multimap<int, std::shared_ptr<Node>> roots;
	std::shared_ptr<Node> x = head;
	while (x != nullptr)
	{
		roots.insert(make_pair(x->Degree, x));
		x = x->Sibling;
	}

	x = other.head;
	while (x != nullptr)
	{
		roots.insert(make_pair(x->Degree, x));
		x = x->Sibling;
	}

	for (std::multimap<int, std::shared_ptr<Node>>::iterator it = roots.begin(); it != roots.end(); ++it)
	{
		std::multimap<int, std::shared_ptr<Node>>::iterator temp = it;
		++temp;
		if (temp != roots.end())
			it->second->Sibling = temp->second;
		else
			it->second->Sibling = nullptr;
	}

	head = roots.begin()->second;
}

template<typename PriorityType, typename VertexData>
void BinomialHeap<PriorityType, VertexData>::BinomialHeap_Union(BinomialHeap<typename PriorityType, typename VertexData>& other)
{
	BinomialHeap_Merge(other);
	if (head == nullptr)
		return;

	NodeX x(head);

	while (x.Next != nullptr)
	{
		if (x.Current->Degree != x.Next->Degree || (x.Next->Sibling != nullptr && x.Next->Sibling->Degree == x.Current->Degree))
		{
			x.Previous = x.Current;
			x.Current = x.Next;
		}
		else
		{
			if (x.Current->Priority <= x.Next->Priority)
			{
				x.Current->Sibling = x.Next->Sibling;
				Binomial_Link(x.Next, x.Current);
			}
			else
			{
				if (x.Previous == nullptr)
				{
					head = x.Next;
				}
				else
				{
					x.Previous->Sibling = x.Next;
				}
				Binomial_Link(x.Current, x.Next);
				x.Current = x.Next;
			}
		}

		x.Next = x.Current->Sibling;

	}
}

template<typename PriorityType, typename VertexData>
TErrorType BinomialHeap<PriorityType, VertexData>::BinomialHeap_DecreasePriority(Handle& handle, PriorityType newPriority)
{
	std::weak_ptr<Node> x = handle.ptr;
	std::shared_ptr<Node> sharedx = x.lock();
	if (sharedx == nullptr)
		return ET_RottenHandle;

	if (newPriority > sharedx->Priority)
		return ET_TooBigPriority;

	sharedx->Priority = newPriority;

	std::shared_ptr<Node> y = sharedx;

	while ((y != nullptr) && (y->Parent.lock() != nullptr) && (y->Priority < y->Parent.lock()->Priority))
	{

		std::shared_ptr<Node> y_Parent = y->Parent.lock();
		std::shared_ptr<Node> y_Sibling = y->Sibling;
		std::shared_ptr<Node> y_Parent_Parent = y_Parent->Parent.lock();

		std::shared_ptr<Node> y_Child = y->Child;
		while (y_Child != nullptr)
		{
			y_Child->Parent = y_Parent;
			y_Child = y_Child->Sibling;
		}

		std::shared_ptr<Node> child = y_Parent->Child;
		while (child != nullptr)
		{
			if (child != y)
				child->Parent = y;

			if (child->Sibling == y)
				child->Sibling = y_Parent;

			child = child->Sibling;
		}

		if (y_Parent_Parent != nullptr)
		{

			child = y_Parent_Parent->Child;
			while (child != nullptr)
			{
				if (child->Sibling == y_Parent)
				{
					child->Sibling = y;
					break;
				}

				child = child->Sibling;
			}
		}

		else
		{

			child = head;
			while (child != nullptr)
			{
				if (child->Sibling == y_Parent)
				{
					child->Sibling = y;
					break;
				}

				child = child->Sibling;
			}
		}

		if (y_Parent == head)
			head = y;

		y->Sibling = y_Parent->Sibling;
		y_Child = y->Child;
		int y_Degree = y->Degree;
		
		if (y == y_Parent->Child)
			y->Child = y->Parent.lock();
		else
			y->Child = y_Parent->Child;

		y_Parent->Child = y_Child;
		y_Parent->Sibling = y_Sibling;
		y_Parent->Parent = y;
		y->Parent = y_Parent_Parent;
		y->Degree = y_Parent->Degree;
		y_Parent->Degree = y_Degree;

		if (y_Parent_Parent != nullptr)
			y_Parent_Parent->Child = y;
	}

	
	return ET_NoError;
}